package unionfind;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给出方程式 A / B = k, 其中 A 和 B 均为代表字符串的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。
 *
 * 示例 :
 * 给定 a / b = 2.0, b / c = 3.0
 * 问题: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 
 * 返回 [6.0, 0.5, -1.0, 1.0, -1.0 ]
 *
 * 输入为: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries(方程式，方程式结果，问题方程式)， 其中 equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。 返回vector<double>类型。
 *
 * 基于上述例子，输入如下：
 *
 * equations(方程式) = [ ["a", "b"], ["b", "c"] ],
 * values(方程式结果) = [2.0, 3.0],
 * queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
 * 输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/evaluate-division
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

public class CalcEquation {

    class Node{
        Node parent;
        double val;

        Node(double v){
            val = v;
            parent = this;
        }
    }

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

        if(equations == null || equations.size() == 0 || values == null || values.length == 0 || queries == null
        || queries.size() == 0){
            return null;
        }
        double[] res = new double[queries.size()];
        Map<String, Node> map = new HashMap<>();
        int i = 0;
        for(List<String> list: equations){
            String first = list.get(0);
            String second = list.get(1);
            Node nodeA = map.get(first);
            if(nodeA == null){
                nodeA = new Node(values[i]);
                map.put(first, nodeA);
            }
            Node nodeB = map.get(second);
            if(nodeB == null){
                nodeB = new Node(1.0);
                map.put(second, nodeB);
            }
            merge(nodeA, nodeB, values[i], map);
            i ++;
        }

        for(i = 0; i < queries.size(); i ++){
            String s1 = queries.get(i).get(0);
            String s2 = queries.get(i).get(1);
            Node n1 = map.get(s1);
            Node n2 = map.get(s2);
            if(n1 == null || n2 == null || getRoot(n1) != getRoot(n2)){
                res[i] = -1.0;
            } else {
                res[i] = n1.val /n2.val;
            }

        }
        return res;
    }

    private Node getRoot(Node n){
        Node root = n.parent;
        while(root.parent != root){
            root = root.parent;
        }
        n.parent = root;
        return root;
    }

    private void merge(Node a, Node b, double value, Map<String, Node> map){
        Node rootA = getRoot(a);
        Node rootB = getRoot(b);
        double ratio = b.val * value / a.val;
        for(Map.Entry<String, Node> entry: map.entrySet()){
            if(getRoot(entry.getValue()) == rootA){
                entry.getValue().val *= ratio;
            }
        }
        rootA.parent = rootB;
    }
}
